We have developed a new and highly robust algorithm for Sparse Multidimensional Iterative Lineshape-Enhanced (SMILE) reconstruction of both non-uniformly sampled and conventional NMR data. Although the concept of only sampling a small subset of the time domain NMR data, followed by non-linear processing, was introduced three decades ago, none of the reconstruction algorithms were sufficiently robust for challenging applications. The new program developed represents a large step forward and has been seamlessly integrated in the NIDDK-developed processing package, NMRPipe, which is used world-wide for the majority of advanced multi-dimensional (3D and 4D) processing schemes. For large data sets, the method is robust and demonstrated for sparsities down to ca 1%, and final all-real spectral sizes as large as 300 Gb. Comparison between fully sampled, conventionally processed spectra and randomly selected NUS subsets of this data shows that the reconstruction quality approaches the theoretical limit in terms of peak position fidelity and intensity. SMILE essentially removes the noise-like appearance associated with the point-spread function of signals that are a default of five-fold above the noise level, but impacts the actual thermal noise in the NMR spectra only minimally. Therefore, the appearance and interpretation of SMILE-reconstructed spectra is very similar to that of fully sampled spectra generated by Fourier transformation. For samples that are unstable in the NMR sample tube for the prolonged periods of time needed for data collection, application of the regular NUS sampling protocol yields large artifacts. However, as we demonstrate for a sample of Abeta peptide, undergoing fibril formation, high quality spectra can be reconstructed using the SMILE program by selecting the order in which time domain data points are sampled. In unrelated work, we have developed optimized non-linear least-squares fitting routines which can identify database protein fragments that fit well to experimentally measured parameters, including residual dipolar couplings and chemical shifts. The ability to restrain the alignment tensor magnitude and asymmetry in such searches reduces the number of experimental parameters needed for yielding high quality fragments, thereby expediting the structure determination process.